#include <bits/stdc++.h>
#define int long long
using namespace std;
char buf[(1<<21)+5],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int read() {
	int f=0,x=0;
	char ch=getchar();
	while(!isdigit(ch)) {
		f|=(ch=='-');
		ch=getchar();
	}
	while(isdigit(ch)) {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f?-x:x;
}
int n,m,p,ans;
bool sub1,sub2;
int a[10005],as[10005];
vector<int>q[1124];
bool vis[100005];
void dfs(int x,int jz) {
	ans=max(ans,jz);
	if(x==n+1) {
		return;
	}
	for(int i=1; i<=n; i++) {
		if(vis[i]==0) {
			vis[i]=1;
			int lk=as[i];
			for(int j=0; j<q[i].size(); j++) {
				int v=q[i][j];
				as[v]+=lk;
			}
			dfs(x,jz+as[i]);
			vis[i]=0;
			for(int j=0; j<q[i].size(); j++) {
				int v=q[i][j];
				as[v]-=lk;
			}
		}
	}
}
signed main() {
	freopen("light.in","r",stdin);
	freopen("light.out","w",stdout);
	n=read();
	for(int i=1; i<=n; i++) {
		a[i]=read();
		p+=a[i];
		as[i]=a[i];
	}
	for(int i=1; i<n; i++) {
		int u=read(),v=read();
		if(u!=1&&v!=1) {
			sub2=1;
		}
		if(u!=v+1&&v!=u+1) {
			sub1=1;
		}
		q[u].push_back(v);
		q[v].push_back(u);

	}
	if(sub1==0) {
		for(int i=1; i<=n; i++) {
			int sum=a[i],s=a[i];
			for(int j=i-1; j>=1; j--) {
				s+=a[j];
				sum+=s;
			}
			for(int j=i+1; j<=n; j++) {
				s+=a[j];
				sum+=s;
			}
			ans=max(ans,sum);
		}
		cout<<ans;
		return 0;
	}
	if(sub2==0) {
		p-=a[1];
		ans=a[1]*n+p;
		int s=0;
		for(int i=1; i<=n; i++) {
			int maxx=-114514191981000,pp=0;
			for(int j=2; j<=n; j++) {
				if(a[j]>maxx) {
					maxx=a[j];
					pp=j;
				}
			}
			s+=a[pp];
			p-=a[pp];
			ans=max(ans,(a[1]+s)*(n-i)+p+s);
			a[pp]=-114514191981000;
		}
		cout<<ans;
		return 0;
	}
	if(n<=10) {
		dfs(1,0);
		cout<<ans;
		return 0;
	}
	sort(a+1,a+n+1);
	int s=0;
	for(int i=n; i>=1; i--) {
		s+=a[i];
		ans+=s;
	}
	cout<<ans;
	return 0;
}
